// 物理内存分配器
// 为用户进程、内核栈、页表页、管道缓冲区等分配物理内存，分配大小为4096字节

#include "types.h"
#include "param.h"
#include "memlayout.h"
#include "spinlock.h"
#include "riscv.h"
#include "defs.h"

void freerange(void *pa_start, void *pa_end);

// 内核结束地址，由kernel.ld定义. 从该地址开始可以分配
extern char end[];

// 物理页链表节点
struct run {
  struct run *next;
};

// 物理页空闲链表
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem;

void kinit() {
  initlock(&kmem.lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

// 释放[pa_start, pa_end)之间的物理页
void freerange(void *pa_start, void *pa_end) {
  char *p;
  p = (char*)PGROUNDUP((uint64)pa_start);
  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE) {
    kfree(p);
  }
}

// 释放pa开始的物理页
void kfree(void *pa) {
  struct run *r;

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");
  
  // 填充垃圾数据，防止悬空引用
  memset(pa, 1, PGSIZE);
  
  r = (struct run*)pa;

  // 采用头插法将物理页添加到空闲链表中
  acquire(&kmem.lock);
  r->next = kmem.freelist;
  kmem.freelist = r;
  release(&kmem.lock);
}

// 分配一个4096字节的物理页；返回一个内核可以使用的指针；如果内存无法分配，返回0
void * kalloc(void) {
  struct run *r;

  acquire(&kmem.lock);
  r = kmem.freelist;
  if(r)
    kmem.freelist = r->next;
  release(&kmem.lock);

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}
